/*
 * @Author: your name
 * @Date: 2024-06-03 15:26:54
 * @LastEditTime: 2024-06-03 15:47:47
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\435.无重叠区间.cpp
 */
/*
 * @lc app=leetcode.cn id=435 lang=cpp
 *
 * [435] 无重叠区间
 */

// @lc code=start
class Solution {
public:
    static bool cmp(vector<int>&a, vector<int>&b){
        if(a[0] == b[0]){
            return a[1] < b[1];
        }
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 记录上一个有效区间的右边界。
        int last_right_index = 0;
        // 记录移除区间的数量
        int count;
        sort(intervals.begin(), intervals.end(), cmp);
        last_right_index = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++){
            // 
            if(intervals[i][0] < last_right_index){
                last_right_index = min(intervals[i][1], last_right_index);
                count++;

            }else{
                // 更新上一个有效区间的右边界。
                last_right_index = intervals[i][1];
            }
        }
        return count;
    }
    
};
// @lc code=end

